package NO6_Tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 2025-6-26
 * 力扣 - 94. 二叉树的中序遍历
 * <p>
 * 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
 */
public class InorderTraversalMain {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));
        System.out.println(inorderTraversal(root));
    }

    // 中序遍历 ： 一直往左，然后中间，最后往右
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> dataList = new ArrayList<>();
        traverse(root, dataList);
        return dataList;
    }
    private static void traverse(TreeNode root, List<Integer> dataList) {
        if (root == null) {
            return;
        }
        // 遍历左树
        traverse(root.left, dataList);
        // 存储当前节点
        dataList.add(root.val);
        // 遍历右树
        traverse(root.right, dataList);
    }
}
